package com.wk.data.graph;
/**
 * 邻接矩阵实现无向图
 * a b c d e f顶点
 */
public class MatrixNDGraph {
	int size;//图顶点个数
	char[] vertexs;//图顶点名称
	int[][] matrix;//邻接矩阵描述边
	
	public MatrixNDGraph(char[] vertexs,char[][] edges) {
		size = vertexs.length;
		this.vertexs = vertexs;
		this.matrix = new int[size][size];
		for (char[] cs : edges) {
			int x = getPosition(cs[0]);
			int y = getPosition(cs[1]);
			matrix[x][y] = 1;
			matrix[y][x] = 1;
		}
	}
	//图的遍历输出
    public void print(){
    	for (int i = 0; i < vertexs.length; i++) {
    		if(i==0) {
    			System.out.print("  ");
    		}
    		System.out.print(vertexs[i]+" ");
		}
    	System.out.println();
    	int index = 0;
        for(int[] i:matrix){
        	System.out.print(vertexs[index]+" ");
            for(int j:i){
                System.out.print(j+" ");
            }
            System.out.println();
            index++;
        }
    }
	private int getPosition(char ch) {
		for (int i = 0; i < vertexs.length; i++) {
			if(vertexs[i] == ch) {
				return i;
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
		char[][] edges = new char[][]{
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'D', 'G'},
            {'I','J'},
            {'J','G'},};
            
        MatrixNDGraph pG;
        // 自定义"图"(输入矩阵队列)
        // 采用已有的"图"
        long start=System.nanoTime();

//        for(int i=0;i<10000;i++){
            pG = new MatrixNDGraph(vertexs, edges);
            pG.print();   // 打印图 
//        }

        long end=System.nanoTime();

        System.out.println((end-start)+"ns");
	}
}
